from sys import maxsize
from time import time
from random import random, randint, sample
from gene import Gene
from population import Population
from individual import Individual
import helpers

"""
Produz uma geração.
1. Parte da geração é produzida via elitismo.
2. Parte da geração é produzida via crossover.
3. Mutações são introduzidas na nova geração.
"""
def evolve(pop, tourn_size, mut_rate):
    new_generation = Population([])
    pop_size = len(pop.individuals)
    elitism_num = pop_size // 2

    # 1. Elitismo: MOVE O MELHOR INDIVÍDUO DESTA PARA UMA PRÓXIMA GERAÇÃO.
    for _ in range(elitism_num):
        fittest = pop.get_fittest()
        new_generation.add(fittest)
        pop.rmv(fittest)

    # 2. Crossover: CRUZAMENTO DE DOIS INDIVÍDUOS SELECIONADOS VIA TORNEIO.
    for _ in range(elitism_num, pop_size):
        parent_1 = selection(new_generation, tourn_size) # OBTÉM PRIMEIRO PAI USANDO O MÉTODO DO TORNEIO.
        parent_2 = selection(new_generation, tourn_size) # OBTÉM SEGUNDO PAI USANDO O MÉTODO DO TORNEIO.
        child = crossover(parent_1, parent_2)            # CRUZA OS DOIS SELECIONADOS.
        new_generation.add(child)                        # ADICIONA PROLE À NOVA GERAÇÃO.

    # 3. Mutação: INTRODUZ MUTAÇÕES NOS INDIVÍDUOS DESTA GERAÇÃO QUE ACABOU DE SER CRIADA.
    for i in range(elitism_num, pop_size):
        mutate(new_generation.individuals[i], mut_rate)

    return new_generation

"""
Retorna um novo indivíduo ao cruzar os genes de dois indivíduos pais.
"""
def crossover(parent_1, parent_2):
    def fill_with_parent1_genes(child, parent, genes_n):
        start_at = randint(0, len(parent.genes)-genes_n-1)
        finish_at = start_at + genes_n
        for i in range(start_at, finish_at):
            child.genes[i] = parent_1.genes[i]

    def fill_with_parent2_genes(child, parent):
        j = 0
        for i in range(0, len(parent.genes)):
            if child.genes[i] == None:
                while parent.genes[j] in child.genes:
                    j += 1
                child.genes[i] = parent.genes[j]
                j += 1

    genes_n = len(parent_1.genes)
    child = Individual([None for _ in range(genes_n)])
    fill_with_parent1_genes(child, parent_1, genes_n // 2)
    fill_with_parent2_genes(child, parent_2)

    return child

"""
Causa mutação nos genes de um invidívuo a uma dada taxa (rate).
"""
def mutate(individual, rate):
    for _ in range(len(individual.genes)):
        if random() < rate:
            sel_genes = sample(individual.genes, 2)
            individual.swap(sel_genes[0], sel_genes[1])


"""
Obtém certa quantidade (`competitors_n`) de indivíduos aleatórios de uma dada população (population) e RETORNA O MAIS APTO desta amostra.
Utiliza método do torneio.
Será utilizada para buscar os mais aptos para o cruzamento.
"""
def selection(population, competitors_n):
    return Population(sample(population.individuals, competitors_n)).get_fittest()

"""
ALGORITMO GENÉTICO.
"""
def run_ga(genes, pop_size, n_gen, tourn_size, mut_rate):
    population = Population.gen_individuals(pop_size, genes) # Gera população inicial.
    history = {'cost': [population.get_fittest().travel_cost]}
    estagnado, generations, min_cost = 0, 0, maxsize

    print("[*] Evoluindo população...")

    start_time = time()
    while estagnado < n_gen: # Executa até o limite (limite de gerações estagnadas (geração igual ou pior do que a anterior))
        population = evolve(population, tourn_size, mut_rate) # Simula evolução: Nova geração.
        cost = population.get_fittest().travel_cost           # Obtém o melhor indivíduo da população e o travel_cost dos genes (cidades) deste.

        if cost < min_cost: # Novo melhor custo?
            estagnado, min_cost = 0, cost # Graças a um novo menor custo, saímos da condição de estagnados (geração igual ou pior do que a anterior).
        else:
            estagnado += 1  # Aumenta contador de estagnado (geração igual ou pior do que a anterior)

        generations += 1 # Incrementa contador total de gerações.
        history['cost'].append(cost)

    total_time = round(time() - start_time, 6)

    print("[!] Evolução finalizada após {} gerações e {} segundos!".format(generations, total_time))
    print("[!] Custo mínimo encontrado de {} km.".format(min_cost))

    history['generations'] = generations
    history['total_time'] = total_time
    history['route'] = population.get_fittest()
    history['route'].genes.append(history['route'].genes[0]) # Considera volta à primeira cidade na rota a ser imprimida. O custo também é calculado de acordo.

    return history